package class05;

// 这道题直接在leetcode测评：
// https://leetcode.com/problems/count-of-range-sum/
public class Code01_CountOfRangeSum {

	// 计算数组中范围和在[lower, upper]之间的子数组个数
	// 使用前缀和 + 归并排序的方法实现
	public static int countRangeSum(int[] nums, int lower, int upper) {
		if (nums == null || nums.length == 0) {
			return 0;
		}
		// 构建前缀和数组，sum[i]表示从nums[0]到nums[i]的累加和
		long[] sum = new long[nums.length];
		sum[0] = nums[0];
		for (int i = 1; i < nums.length; i++) {
			sum[i] = sum[i - 1] + nums[i];
		}
		// 通过归并排序的思想处理前缀和数组
		return process(sum, 0, sum.length - 1, lower, upper);
	}

	// 递归处理函数，在sum数组的[L, R]范围内统计范围和在[lower, upper]之间的子数组个数
	public static int process(long[] sum, int L, int R, int lower, int upper) {
		// 基础情况：只有一个元素
		if (L == R) {
			// 判断该元素值是否在指定范围内
			return sum[L] >= lower && sum[L] <= upper ? 1 : 0;
		}
		// 分治处理：将数组分为两部分
		int M = L + ((R - L) >> 1);
		// 左半部分的结果 + 右半部分的结果 + 跨越中点的结果
		return process(sum, L, M, lower, upper) + process(sum, M + 1, R, lower, upper)
				+ merge(sum, L, M, R, lower, upper);
	}

	// 合并过程中统计跨越中点的子数组个数，并完成排序
	// arr数组在[L, M]和[M+1, R]两个区间内分别有序
	public static int merge(long[] arr, int L, int M, int R, int lower, int upper) {
		// 存储满足条件的子数组个数
		int ans = 0;
		
		// 滑动窗口的左右边界，用于统计满足条件的范围
		int windowL = L;
		int windowR = L;
		// [windowL, windowR)
		for (int i = M + 1; i <= R; i++) {
			// 对于以arr[i]结尾的子数组，其范围和为 arr[i] - arr[x] (L <= x <= M)
			// 需要满足 lower <= arr[i] - arr[x] <= upper
			// 即需要找到满足 arr[i] - upper <= arr[x] <= arr[i] - lower 的arr[x]个数
			long min = arr[i] - upper;
			long max = arr[i] - lower;
			
			// 找到右边界，使得arr[windowR-1] <= max
			while (windowR <= M && arr[windowR] <= max) {
				windowR++;
			}
			// 找到左边界，使得arr[windowL] >= min
			while (windowL <= M && arr[windowL] < min) {
				windowL++;
			}
			// 此时[windowL, windowR)范围内所有元素都满足条件
			ans += windowR - windowL;
		}
		
		// 标准归并排序的合并过程，将两个有序数组合并为一个有序数组
		long[] help = new long[R - L + 1];
		int i = 0;
		int p1 = L;
		int p2 = M + 1;
		// 比较两个子数组的元素，将较小的元素放入辅助数组
		while (p1 <= M && p2 <= R) {
			help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
		}
		// 将左半部分剩余元素复制到辅助数组
		while (p1 <= M) {
			help[i++] = arr[p1++];
		}
		// 将右半部分剩余元素复制到辅助数组
		while (p2 <= R) {
			help[i++] = arr[p2++];
		}
		// 将辅助数组内容复制回原数组，完成排序
		for (i = 0; i < help.length; i++) {
			arr[L + i] = help[i];
		}
		return ans;
	}

}
